﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ArraysAndStrings.Merge
{
    class MainProject
    {
        static void Main(string[] args)
        {
            int[][] nums = new int[][]
            {
                new int[] { 2,3} ,
                new int[] { 4,5} ,
                new int[] { 6,7} ,
                new int[] { 8,9} ,
                new int[] { 1,10} ,
            };
            int[][] arr = Merge(nums);
            foreach (var array in arr)
            {
                foreach (var item in array)
                {
                    Console.WriteLine(item);
                }
                Console.WriteLine("----------------");
            }
            Console.ReadKey();
        }
        public static int[][] Merge(int[][] intervals)
        {
            if (intervals.Length == 1)
            {
                return intervals;
            }
            for (int i = 0; i < intervals.Length - 1; i++)
            {
                for (int j = 0; j < intervals.Length - 1 - i; j++)
                {
                    if (intervals[j][0] > intervals[j + 1][0])
                    {
                        int[] temp = intervals[j];
                        intervals[j] = intervals[j + 1];
                        intervals[j + 1] = temp;
                    }
                }
            }

            List<int[]> returnArray = new List<int[]>();
            int leftBoard = intervals[0][0];
            int rightBoard = intervals[0][1];

            for (int i = 1; i < intervals.Length; i++)
            {
                //14 01
                if (leftBoard <= intervals[i][0] && intervals[i][1] <= rightBoard)
                {
                    if (i == intervals.Length - 1)
                    {
                        returnArray.Add(new int[2] { leftBoard, rightBoard });
                    }
                    continue;
                }
                else if(leftBoard <= intervals[i][0] && intervals[i][0] <= rightBoard && intervals[i][1] > rightBoard)
                {
                    rightBoard = intervals[i][1];
                }
                else if (leftBoard <= intervals[i][1] && intervals[i][1] <= rightBoard && rightBoard > intervals[i][1])
                {
                    leftBoard = intervals[i][0];
                }
                else if(leftBoard >= intervals[i][0] && intervals[i][1] >= rightBoard)
                {
                    leftBoard = intervals[i][0];
                    rightBoard = intervals[i][1];
                }
                else
                {
                    //不在区间内
                    returnArray.Add(new int[2] { leftBoard, rightBoard });
                    leftBoard = intervals[i][0];
                    rightBoard = intervals[i][1];
                }
                if (i== intervals.Length-1)
                {
                    returnArray.Add(new int[2] { leftBoard, rightBoard });
                }
            }
            return returnArray.ToArray();
        }
    }
}
